package eashrine;

import org.junit.jupiter.api.Test;
import tool.s;

/**
 * @Author: Siantar
 * @Date: 2023-11-19-21:59
 * @Description: 1.0
 */
public class T0689 {
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
//        s.print(nums);
        int n = nums.length;
        int[] ns = new int[n];
        int t = 0;
        for (int i = 0; i < n; i++) {
            t += nums[i];
            if (i >= k - 1) {
                ns[i] = t;
                t -= nums[i - k + 1];
            }
        }
//        s.print(ns);
        int[] dp1MaxSum = new int[n];
        int[] dp1MaxIndex = new int[n];
        dp1MaxSum[k - 1] = ns[k - 1];
        dp1MaxIndex[k - 1] = 0;
        for (int i = k; i < n; i++) {
            if (ns[i] > dp1MaxSum[i - 1]) {
                dp1MaxSum[i] = ns[i];
                dp1MaxIndex[i] = i - k + 1;
            } else {
                dp1MaxSum[i] = dp1MaxSum[i - 1];
                dp1MaxIndex[i] = dp1MaxIndex[i - 1];
            }
        }
//        s.print(dp1MaxSum);
//        s.print(dp1MaxIndex);
        int[] dp2MaxSum = new int[n];
        int[][] dp2MaxIndex = new int[n][2];
        dp2MaxSum[2 * k - 1] = ns[k - 1] + ns[2 * k - 1];
        dp2MaxIndex[2 * k - 1] = new int[]{0, k};
        for (int i = 2 * k; i < n; i++) {
            if (ns[i] + dp1MaxSum[i - k] > dp2MaxSum[i - 1]) {
                dp2MaxSum[i] = ns[i] + dp1MaxSum[i - k];
                dp2MaxIndex[i][0] = dp1MaxIndex[i - k];
                dp2MaxIndex[i][1] = i - k + 1;
            } else {
                dp2MaxSum[i] = dp2MaxSum[i - 1];
                dp2MaxIndex[i][0] = dp2MaxIndex[i - 1][0];
                dp2MaxIndex[i][1] = dp2MaxIndex[i - 1][1];
            }
        }
//        s.print(dp2MaxSum);
//        s.print2(dp2MaxIndex);
        int[] dp3MaxSum = new int[n];
        int[][] dp3MaxIndex = new int[n][3];
        dp3MaxSum[3 * k - 1] = ns[k - 1] + ns[2 * k - 1] + ns[3 * k - 1];
        dp3MaxIndex[3 * k - 1] = new int[]{0, k, 2 * k};
        for (int i = 3 * k; i < n; i++) {
            if (ns[i] + dp2MaxSum[i - k] > dp3MaxSum[i - 1]) {
                dp3MaxSum[i] = ns[i] + dp2MaxSum[i - k];
                dp3MaxIndex[i][0] = dp2MaxIndex[i - k][0];
                dp3MaxIndex[i][1] = dp2MaxIndex[i - k][1];
                dp3MaxIndex[i][2] = i - k + 1;
            } else {
                dp3MaxSum[i] = dp3MaxSum[i - 1];
                dp3MaxIndex[i][0] = dp3MaxIndex[i - 1][0];
                dp3MaxIndex[i][1] = dp3MaxIndex[i - 1][1];
                dp3MaxIndex[i][2] = dp3MaxIndex[i - 1][2];
            }
        }
//        s.print(dp3MaxSum);
//        s.print2(dp3MaxIndex);
//        System.out.println();
        return dp3MaxIndex[n - 1];
    }
    @Test
    public void test() {
        s.print(maxSumOfThreeSubarrays(new int[]{1,2,1,2,6,7,5,1},2));
    }
}
